Flipping Signs
これは不可能
ある数$ iについて、$ A_iを負にしたい場合、$ A_{i+1}を負にする必要がある
$ A_{i+1}は選んだ数ではないから正に戻す必要がある
$ A_{i+2}を負にする必要が生じる
これを繰り返すと、$ A_iと$ A_N-1が負になる
大きい数を引き去ったら、減りが大きい
小さい数を引き去るのが良い
後から読むと、この考え方は問題の解答とは違いそうt6o_o6t.icon
今回の問題でいえば、引き去る対象が正になってしまうなら、そもそも引き去らなくて良いということ
補足
注意点として、Aは負になりうる
負の数を先に引き去れば、和はむしろ増える
このケースも、Aをソートして小さい順に引いていけば問題ない
負の数は全て引き去るのが良い
注意すべきケースは、負の数が奇数個あるとき
https://scrapbox.io/files/65086f44045fe0001b2c4556.png
この図の状態で、-1は$ 2m+1個目の負数とする
-1と3を両方引き去ると、-2になって減ってしまう
-4と3だったら、+1となって増えるので良い。
Nが小さいので、小さい順に線形に見ていく
2つずつ数を見ていく
もし、数の和が負であれば、引く
数の和が正であれば、足す
書いている途中で、奇数個の処理の必要性に気づいた
忘れがち